import sortedcontainers
sortedcontainers.SortedList
import collections
class Solution:
    def maximumSubarraySum(self, nums, k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        d = collections.defaultdict(list)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
            d[nums[i]].append(i)
        max_ans = -float('inf')
        key_set = set(d.keys())
        for key in key_set:
            if key + k in key_set:
                if key == 16:
                    print(1)
                l1 = d[key]
                l2 = d[key + k]
                m1 = len(l1)
                m2 = len(l2)
                index0 = 0
                index1 = 0
                pre_min = float('inf')
                while index1 < m2 and index0 < m1: 
                    if l1[index0] < l2[index1]:
                        pre_min = min(pre_min, prefix[l1[index0]])
                        max_ans = max(max_ans, prefix[l2[index1] + 1] - pre_min)
                        index0 += 1
                    else:
                        # max_ans = max(max_ans, prefix[l2[index1] + 1] - pre_min)
                        index1 += 1
                while index1 < m2:
                    max_ans = max(max_ans, prefix[l2[index1] + 1] - pre_min)
                    index1 += 1
            if key - k in key_set:
                l1 = d[key]
                l2 = d[key - k]
                m1 = len(l1)
                m2 = len(l2)
                index0 = 0
                index1 = 0
                pre_min = float('inf')
                while index1 < m2 and index0 < m1: 
                    if l1[index0] < l2[index1]:
                        pre_min = min(pre_min, prefix[l1[index0]])
                        max_ans = max(max_ans, prefix[l2[index1] + 1] - pre_min)
                        index0 += 1
                    else:
                        max_ans = max(max_ans, prefix[l2[index1] + 1] - pre_min)
                        index1 += 1
                while index1 < m2:
                    max_ans = max(max_ans, prefix[l2[index1] + 1] - pre_min)
                    index1 += 1                
        return max_ans   
                    
data = Solution()   
nums = [16,23,79,78,68,16,32,96,73,22,26,71,48,89,89,50,22,89,3,30,16]
k = 6
# nums = [-47,-2,98,66,70,-76,76,-49,-19,-91,-1,-93,-58,-61,4,60,-83,-26,34,-11,-27,-62,-85,87,-4,24,-90,-50,63,-6,-44,-48,93,-80,17,91,-99,-68,60,91,-26,-98,-86,-69,28,-14,-86,-26,-63,32,-77,-60,35,-82,-17,27,-68,-74,-17,-42,3,51,90,32,-53,-67,-92,11,-48,72,33,81,-61,-61,11,30,-47,-9,64,44,-9,97,69,-21,-26,59,-41,95,-41,-38,-61,9,27,20,-24,50,-82,-61,-60,51,-28,-3,-11,-83,-50,-90,-23,-19,65,45,12,-22,3,24,91,54,-73,-60,24,72,80,-16,44,-82,29,-40,-52,95,-72,-20,-100,-27,66,35,58,95,2,41,-43,54,-19,43,99,83,0,-91,-56,45,-20,-87,-97,71,45,-13,10,99,-23,-18,-34,63,-24,-19,-72,33,-12,33,-27,27,-22,-54,33,-61,-89,50,35,67,-98,82,28,74,-29,-40,-49,60,-31,29,5,61,-1,-77,-54,75,29,21,-23,84,-73,-75,48,-65,-60,42,-3,-77,55,-45,14,-47,34,24,86,-43,-9,-49,-43,-74,30,-27,78,3,0,-53,-16,37,-4,-89,45,100,-89,-74,98,6,43,-89,-98,-69,34,83,49,-20,39,-14,84,32,-86,13,49,8,49,-15,50,76,-32,47,-98,99,41,-85,69,60,-69,-85,-29,95,69,-14,-1,-2,-5,-37,99,80,-93,-54,-28,-85,47,-78,55,-56,-49,-24,-43,84,-18,55,-59,-45,-64,-69,44,40,-93,-62,68,-88,-8,-31,-35,-89,-76,55,-31,10,-82,54,-57,56,28,-80,-50,9,-33,-65,-29,36,60,73,-13,61,-10,64,43,41,-17,85,-80,-43,-54,-74,-70,92,87,-92,89,9,-37,63,-44,63,-51,39,-22,-91,-76,83,33,-39,-16,-25,-92,72,-28,0,-50,-25,-59,-1,-22,61,38,45,-65,16,99,-18,-23,-57,-59,-14,-60,-89,-38,-6,-73,90,24,91,-53,85,9,-82,-94,36,-6,53,88,-88,-86,82,44,50,54,9,-95,75,-65,-28,60,-33,12,100,40,76,16,39,-84,98,8,-71,-89,-72,-66,-98,4,-94,-15,47,-1,30,-47,-73,24,-37,48,-12,-15,-62,-7,-65,-100,63,-38,75,-84,68,87,-25,-32,-79,82,-7,-38,40,68,27,63,-97,-56,20,-76,-77,-32,17,33,-52,89,-92,13,-41,89,-19,0,-21,75,-13,34,-17,-17,25,47,-18,87,80,-75,92,84,2,68,18,26,40,57,-95,25,-74,-2,-78,-66,53,-42,-59,99,87,68,91,84,-73,37,52,-71,-53,-78,23,-63,-99,-57,-28,-67,-45,21,-58,77,19,64,85,66,-5,-6,-83,53,48,-26,-56,-42,24,1,70,34,48,-43,-73,-80,77,-32,-90,-23,-95,86,7,-96,-20,-11,-50,-89,98,-30,15,-41,-39,42,71,-31,13,34,59,-94,-84,97,-29,-16,62,57,-29,-85,-54,-63,-2,-52,21,-14,-70,-68,-7,21,84,49,-54,-70,0,2,-16,68,31,-62,-44,75,53,32,10,44,41,-65,96,-16,-19,46,-63,-96,11,-57,-82,-97,53,-54,11,70,9,53,47,61,-32,98,74,24,80,-10,-45,-81,-39,-78,-84,70,-17,-89,-53,24,-86,-60,76,-10,-75,-91,5,-90,-63,-12,-40,77,25,16,-39,71,-22,-62,-13,45,96,62,-47,89,72,85,67,47,-1,-55,-17,98,-2,95,-58,-49,-64,13,86,92,79,99,3,-15,-98,4,-38,-46,21,-90,-83,-62,-20,74,-61,92,-91,-35,-67,13,-79,42,86,-44,-1,87,-30,-69,53,-11,-11,-77,88,52,-26,-36,-41,82,67,-25,-27,90,52,-63,-52,-20,-5,-34,93,34,26,97,-6,67,73,81,25,-49,31,-68,-8,-1,14,7,-38,-6,-41,99,-57,31,72,-28,58,40,89,85,76,-49,11,-13,-99,89,-76,-35,99,-38,33,-36,3,26,-95,-80,-66,-19,22,13,8,-27,-5,79,45,84,38,-51,-64,35,-45,6,39,-74,-87,98,-40,91,46,42,24,-55,-63,54,88,57,88,-65,-91,42,94,0,23,-42,2,61,76,77,-84,100,-58,89,72,76,83,-87,82,94,-40,62,-74,-88,74,-84,21,-36,24,13,8,62,58,29,-27,-43,25,-53,32,11,73,-26,6,77,99,-53,-28,-25,79,-1,53,15,66,56,96,-41,-21,-48,43,42,47,-12,-7,49,21,-7,85,73,-29,-48,-5,0,-62,-74,65,-91,98,-9,63,47,-83,-27,-10,48,-23,-43,-92,-90,17,61,-11,-12,46,-29,-31,58,-81,66,18,63,55,24,80,-22,-88,24,-68,74,-16,-6,-29,3,-63,-15,-6,85,34,21,-61,-99,-70,17,72,62,-54,49,-55,16,-73,41,85,24,-40,71,-82,77,8,8,-38,58,81,99,-47,12,69,-8,24,31,-86,76,-14,-31,77,-25,26,-67,97,98,-8,-43,-89,99,22,-29,-54,-87,22,80,-52,48,48,24,86,94,38,-35,-49,-29,55,39,-12,14,-31,33,23,29,52,-54,1,-79,40,-87,71,67,-90,97,-4,41,66,47,-51,-78,-84,-60,9,-40,47,-28,53]
# k = 14
print(data.maximumSubarraySum(nums, k))     
                    
                    
                    
                    
        
            
                
                
                
        
        